package pe.com.nextel.util;
/**
 * This class contains various methods for manipulating arrays (such as
 * sorting and searching).  It also contains a static factory that allows
 * arrays to be viewed as lists.<p>
 *
 * The documentation for the sorting and searching methods contained in this
 * class includes briefs description of the <i>implementations</i>.  Such
 * descriptions should be regarded as <i>implementation notes</i>, rather than
 * parts of the <i>specification</i>.  Implementors should feel free to
 * substitute other algorithms, so long as the specification itself is adhered
 * to.  (For example, the algorithm used by <tt>sort(Object[])</tt> does not
 * have to be a mergesort, but it does have to be <i>stable</i>.)
 *
 * @author  Josh Bloch
 * @author  eespinoza
 * @version 1.38, 02/06/02
 * @see Comparable
 * @since 1.2
 */
public class Arrays {
    
    /**
     * Tuning parameter: list size at or below which insertion sort will be
     * used in preference to mergesort or quicksort.
     */
    private static final int INSERTIONSORT_THRESHOLD = 7;
    /**
     * Realiza la busqueda de
     * @param arreglo
     * @param dato
     * @return
     */
    public static int find(List list, Comparable dato) {
        int inicio = 0;
        int fin = list.size() - 1;
        int pos;
        while (inicio <= fin) {
            pos = (inicio + fin) / 2;
            if (((Comparable)list.get(pos)).compareTo(dato) == 0) {
                return pos;
            } else if (((Comparable)list.get(pos)).compareTo(dato) < 0) {
                inicio = pos + 1;
            } else {
                fin = pos - 1;
            }
        }
        
        return -1;
    }
    
    public static int find(Comparable[] arreglo, Comparable dato) {
        
        int inicio = 0;
        int fin = arreglo.length - 1;
        int pos;
        while (inicio <= fin) {
            pos = (inicio + fin) / 2;
            if (arreglo[pos].compareTo(dato) == 0) {
                return pos;
            } else if (arreglo[pos].compareTo(dato) < 0) {
                inicio = pos + 1;
            } else {
                fin = pos - 1;
            }
        }
        arreglo = null;
        return -1;
    }
    
    /**
     *  si es 0 a mas lo encontro
     *  si es -2 es menor que todos
     *  si es -1 es es mayor que todos
     *  
     */
    public static int esMayorMenor(List list, Comparable dato) {
        
        //Comparable[] arreglo = (Comparable[]) list.toArray();
        boolean esmayor = false;
        boolean esmenor = false;
        
        int inicio = 0;
        int fin = list.size() - 1;
        int pos;
        while (inicio <= fin) {
            pos = (inicio + fin) / 2;
            if (((Comparable)list.get(pos)).compareTo(dato) == 0) {
                return pos;
            } else if (((Comparable)list.get(pos)).compareTo(dato) < 0) {
                esmenor = true; esmayor=false;
                inicio = pos + 1;
            } else {
                esmayor = true; esmenor=false;
                fin = pos - 1;
            }
        }
        
        if(esmenor) return -2;
        //es mayor
        return -1;
        
    }
    
    /**
     *  si es 0 lo encontro o no existe
     *  si es -1 es menor
     *  si es 1 es es mayor
     */
    public static int esMayorMenor(Comparable[] arreglo, Comparable dato) {
        
        int inicio = 0;
        int fin = arreglo.length - 1;
        int pos;
        while (inicio <= fin) {
            pos = (inicio + fin) / 2;
            if (arreglo[pos].compareTo(dato) == 0) {
                return 0;
            } else if (arreglo[pos].compareTo(dato) < 0) {
                return -1;
            } else {
                return 1;
            }
        }
        arreglo = null;
        return 0;
    }
    
    public static void sort(List list) {
        Object a[] = list.toArray();
        Arrays.sort(a);
        //ListIterator i = list.listIterator();
        for (int j = 0; j < a.length; j++) {
            list.set(j, a[j]);
        }
    }
    
    public static void sort(Object[] a) {
        Object aux[] = new Object[a.length];
        System.arraycopy(a, 0, aux, 0, a.length);
        mergeSort(aux, a, 0, a.length, 0);
    }
    
    /**
     * Src is the source array that starts at index 0
     * Dest is the (possibly larger) array destination with a possible offset
     * low is the index in dest to start sorting
     * high is the end index in dest to end sorting
     * off is the offset to generate corresponding low, high in src
     */
    private static void mergeSort(Object src[], Object dest[],
            int low, int high, int off) {
        int length = high - low;
        
        // Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i = low; i < high; i++) {
                for (int j = i; j > low &&
                        ((Comparable) dest[j - 1]).compareTo((Comparable) dest[j]) > 0; j--) {
                    swap(dest, j, j - 1);
                }
            }
            return;
        }
        
        // Recursively sort halves of dest into src
        int destLow = low;
        int destHigh = high;
        low += off;
        high += off;
        int mid = (low + high) >> 1;
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);
        
        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable) src[mid - 1]).compareTo((Comparable) src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }
        
        // Merge sorted halves (now in src) into dest
        for (int i = destLow,  p = low,  q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable) src[p]).compareTo(src[q]) <= 0) {
                dest[i] = src[p++];
            } else {
                dest[i] = src[q++];
            }
        }
    }
    
    /**
     * Swaps x[a] with x[b].
     */
    private static void swap(Object x[], int a, int b) {
        Object t = x[a];
        x[a] = x[b];
        x[b] = t;
    }
}
